#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from pprint import pprint


def _make_mat(rows, cols, init_value=None):
    one_row = [init_value] * cols
    mat = [list(one_row) for i in range(rows)]

    return mat

def _enough_resource(remain, need):
    for r, n in zip(remain, need):
        if r < n:
            return False

    return True

def add_vector(origin_remain, origin_p_need):
    return list(map(lambda x,y : x+y, origin_remain, origin_p_need))

def sub_vector(origin_remain, origin_p_need):
    return list(map(lambda x,y : x-y, origin_remain, origin_p_need))


class Banker:
    '''
        row : process/thread/worker
        column : resource
    '''
    def __init__(self, claim_max_mat, allocation_mat, resource_total_list):
        self.max = claim_max_mat
        self.alloc = allocation_mat
        self.resource_total = resource_total_list

        # 计算remain_need mat, remain_resource list
        self._calc_others()

    def _calc_others(self):
        self.process_num = len(self.max)
        self.resource_num = len(self.max[0])
        validate = self.validate()

        if not validate:
            # NOTE: 构造函数raise, 对于上层会怎样
            raise "invalid para"

        self.remain_need = _make_mat(self.process_num, self.resource_num)
        self.remain_resource = list(self.resource_total)

        for p in range(self.process_num):
            for r in range(self.resource_num):
                self.remain_need[p][r] = self.max[p][r] - self.alloc[p][r]
                self.remain_resource[r] -= self.alloc[p][r]

                # 等同于 alloc <= max
                assert self.remain_need[p][r] >= 0
        # print(self.remain_resource, '\n\n')

    def validate(self):
        # TODO: 判断传入的几个参数的row, col是否相同
        # 判断resource_tatal 是否大于 每个进程的self.max[p]
        return True

    def is_current_safe(self):
        ret = self.find_one_safety_sequences()
        return bool(ret)

    def is_safe_sequence(self, process_sequence):
        # 传入一个序列, 判断是否是一个安全序列
        # 对序列依次结束尝试结束进程, 并收回alloc资源
        # 如果可以结束所有进程, 表示安全!
        # 如果中间某个进程无法结束, 表示非安全序列
        # NOTE: 结束后不要改变self.remain_resource, self.remain_need等数据结构
        # return : ok, failed_p
        return self._try_sequence(process_sequence)

    def is_safe_request(self, p, require_vector):
        # NOTE: 判断在当前情况下:进程p尝试申请此资源requre_vector后, 系统是否安全
        # 1: 首先判断是否可以获取资源
        # 2: 如果可以, 获取后, 判断系统是否安全
        # 3: 恢复系统数据结构
        if not _enough_resource(self.remain_need[p], require_vector):
            return False, 'bigger than need'

        if not _enough_resource(self.remain_resource, require_vector):
            return False, 'bigger than remain_resource'

        origin_alloc = list(self.alloc[p])
        origin_need = list(self.remain_need[p])
        origin_remain = list(self.remain_resource)

        self.alloc[p] = add_vector(origin_alloc, require_vector)
        self.remain_need[p] = sub_vector(origin_need, require_vector)
        self.remain_resource = sub_vector(origin_remain, require_vector)

        is_safe_cur = self.is_current_safe()

        # restore
        self.alloc[p] = origin_alloc
        self.remain_need[p] = origin_need
        self.remain_resource = origin_remain

        if not is_safe_cur:
            return is_safe_cur, 'not safe alloc'
        else:
            return is_safe_cur, None

    def _try_sequence(self, process_sequence):
        # NOTE: 尽量不修改self.remain_need, 所以也就不需要恢复了
        # 后续都用copy_remain, 避免修改remain_need
        copy_remain = list(self.remain_resource)

        for p in process_sequence:
            # print('=================== try %s  =====================' % p)
            # print('remain: ', self.remain_resource)
            # print('need: ', self.remain_need[p])
            # print('alloc: ', self.alloc[p])
            if not _enough_resource(copy_remain, self.remain_need[p]):
                print('sequence failed at [%s]' % p)
                return False, p

            copy_remain = add_vector(copy_remain, self.alloc[p])

        # return ret, failed_p
        return True, -1

    def _finished(self, p):
        return not any(self.remain_need[p])

    def _num_finished(self):
        count = 0
        for p in range(self.process_num):
            if self._finished(p):
                count += 1

        return count

    def find_one_safety_sequences(self):
        ret_path = []
        rec_ope = self._rec_find_one_safety
        return self._rec_find_one_safety(self.process_num, ret_path, None, rec_ope)

    def find_all_safety_sequences(self):
        # 找出所有的安全序列
        ret_path = []
        results = []
        pprint(results)
        rec_ope = self._rec_find_all_safety
        self._rec_find_all_safety(self.process_num, ret_path, results, rec_ope)
        return results

    def _rec_find_one_safety(self, left_p, ret_path, cus_data, rec_ope):
        if left_p == 0:
            return ret_path

        for p in range(self.process_num):
            ret = self._find_operation(p, left_p, ret_path, cus_data, rec_ope)
            if ret:
                return ret

        return None

    def _rec_find_all_safety(self, left_p, ret_path, results, rec_ope):
        # TODO, NOTE: 如何重构, 提取出和_rec_find_one_safety相同的部分
        if left_p == 0:
            results.append(list(ret_path))
            return ret_path

        for p in range(self.process_num):
            self._find_operation(p, left_p, ret_path, results, rec_ope)

        return None

    def _find_operation(self, p, left_p, ret_path, cus_data, cus_ope):
        # if self._finished(p):
        # 判断p是否在ret_path中, 如果不是, 需要(递归)继续往下处理
        # print('not in %s' % p)
        # NOTE: 这里用 p in ret_path判断是否处理过process
        # 而不是用_finished(p)通过资源need 0判断(因为进程资源need vector都是0, 也可能还没有结束, 还持有alloc)
        if p in ret_path:
            print('already in')
            return

        if not _enough_resource(self.remain_resource, self.remain_need[p]):
            return

        assert p not in ret_path
        # origin_p_need = list(self.remain_need[p])
        origin_remain = list(self.remain_resource)

        # NOTE: 修改这个, 主要是后面判断是否进程已经全部完成
        # 现在通过 left_p 判断, 不再需要修改并恢复 slef.fremain_need[p]
        # self.remain_need[p] = [0] * self.resource_num

        # NOTE: 进程结束后, 收回alloc资源
        # self.remain_resource = cur_remain + alloc
        self.remain_resource = add_vector(origin_remain, self.alloc[p])

        print('left_p %s' % (left_p - 1))
        print('ret_path', ret_path + [p])
        print('remain', self.remain_resource)
        print('===================  =====================')
        # ret = self._rec_find_all_safety(left_p-1, ret_path + [p], cus_data)
        ret = cus_ope(left_p-1, ret_path + [p], cus_data, cus_ope)

        # cus_data: 不同的用途, 传入数据不同, 比如find_one和find_all
        # cus_ope(cus_data)         # 或者cus_ope(), 然后自带闭包, cus_ope 内部包含数据

        # 首先恢复self.remain_need和self.remain_resource
        # 需要恢复left_p吗, 如果是栈变量, 不需要恢复
        # self.alloc 这里进入时不要改变, 所以出来时也不用恢复
        # NOTE: 即使找到了, 也恢复remain_resource和remain_need.
        # NOTE: 因为这里只是判断是否安全, 并不是真的分配资源和执行进程
        self.remain_resource = origin_remain
        # self.remain_need[p] = origin_p_need

        return ret


def test():
    max = [
        [5, 5, 9],
        [5, 3, 6],
        # [0, 0, 0],
        [4, 0, 11],
        [4, 2, 5],
        [4, 2, 4],
    ]

    alloc = [
        [2, 1, 2],
        [4, 0, 2],
        # [0, 0, 0],
        [4, 0, 5],
        [2, 0, 4],
        [3, 1, 4],
    ]

    # remain: 2, 3, 3
    # need = [
    #     [3, 4, 7],
    #     [1, 3, 4],
    #     [0, 0, 6],
    #     [2, 2, 1],
    #     [1, 1, 0]
    # ]

    resource_total = [17, 5, 20]

    b = Banker(max, alloc, resource_total)

    v = b.is_current_safe()
    print('remain_resource : %s' % b.remain_resource)
    print('remain_need : %s' % b.remain_need)
    print('current safe %s' % v)

    # r = b.find_all_safety_sequences()
    # pprint(r)
    # pprint('result nums %s' % len(r))


    print('===================  =====================')
    # is_safe_sequence, failed_p = b.is_safe_sequence([3, 2, 1, 0, 4])
    is_safe_sequence, failed_p = b.is_safe_sequence([1, 2, 3, 0, 4])
    # is_safe_sequence, failed_p = b.is_safe_sequence([3, 2, 1, 4, 0])
    print('safe sequence %s, failed at %s' % (is_safe_sequence, failed_p))

    print('===================  =====================')
    # is_safe_request, failed_reason = b.is_safe_request(3, [2, 0, 1])
    is_safe_request, failed_reason = b.is_safe_request(0, [0, 2, 0])
    print('safe request %s, failed reason: %s' % (is_safe_request, failed_reason))


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
